In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
Bajtazar jest programistą pracującym nad nowym, rewolucyjnym edytorem tekstu. W jego edytorze będą dostępne dwa rodzaje operacji: pierwszy to zwykła edycja tekstu, zaś drugi - cofnięcie jednej z poprzednich operacji. Nowym pomysłem Bajtazara jest wprowadzenie operacji wielopoziomowego cofania, które działa w następujący sposób:
Edycja tekstu to operacja poziomu 0. Operacja cofnięcia poziomu polega na znalezieniu oraz cofnięciu ostatnio wykonanej, nie wycofanej operacji o poziomie albo niższym. W szczególności, cofnięcie poziomu wycofuje ostatnią operację edycji tekstu, zaś cofnięcie poziomu może cofnąć zarówno edycje, jak i cofnięcia poziomu (ale nie cofnięcia wyższych poziomów).
Bardziej formalnie: każda z już wykonanych operacji może być w jednym z dwóch stanów: aktywna, albo wycofana. Niech będzie jedną z operacji. Zaraz po jej wykonaniu, jest aktywna. Jeśli jest operacją cofnięcia poziomu , znajdujemy ostatnią operację aktywną poziomu co najwyżej (oznaczmy ją ) i zmieniamy jej stan na wycofaną. Jeśli sama była operacją cofnięcia i spowodowała wycofanie innej operacji , musimy wtedy przywrócić do stanu aktywnego. Dalej postępujemy według tej samej reguły - jeśli operacja jest operacją cofnięcia i wpłynęła na stan jednej z poprzednich operacji , zmieniamy również stan operacji , oczywiście uwzględniając dalsze skutki tego faktu. Cały ten ciąg czynności kończy się, kiedy osiągniemy operację edycji tekstu.
Dla uproszczenia, całą zawartość tekstu w edytorze będziemy reprezentować przez jedną liczbę całkowitą , zwaną stanem edytora, na początku równą . Dla każdej operacji edycji znany jest stan, do którego doprowadza ona edytor. Stan edytora zależy wyłącznie od ostatniej operacji edycji będącej w stanie aktywnym. Pomóż Bajtazarowi i napisz program, który śledzi stan edytora.
Przeanalizujmy następujący przykład. Poniższa tabela zawiera kilka operacji przeprowadzonych przez Bajtazara oraz stan edytora po każdej z nich. Symbol oznacza operację edycji tekstu zmieniającą stan edytora na , zaś to operacja cofnięcia poziomu .
Operacja | ||||||||||||
Stan edytora | 0 | 1 | 2 | 5 | 2 | 1 | 2 | 4 | 2 | 1 | 0 | 1 |
Na początku Bajtazar wykonał trzy operacje edycji, zmieniające stan edytora najpierw z 0 na 1, potem na 2, w końcu na 5. Potem wykonał dwie operacje cofnięcia poziomu 1 - pierwsza cofnęła operację , zaś druga cofnęła zmieniając ich stan na wycofane. W ten sposób stan edytora powrócił do 1. Kolejną operacją było cofnięcie poziomu 3, które wpłynęło na operację (przez co stała się wycofana), tym samym przywracając operację (czyniąc ją na powrót aktywną). Stan edytora przez to znowu zmienił się na 2. Operacja cofnęła operację , operacja cofnęła (wcześniej przywróconą) operację , przedostatnia operacja () cofnęła operację , zaś ostatnia operacja to , ustalająca stan edytora na 1.
Pierwszy wiersz wejścia zawiera liczbę całkowitą dodatnią , będącą liczbą operacji wykonanych przez Bajtazara. Kolejnych wierszy zawiera opisy operacji, po jednym w każdej linii. Opis składa się z pojedynczej liczby całkowitej (, ). Jeśli , to operacja ta jest edycją tekstu, która zmienia stan edytora na . Jeśli , to jest to operacja cofnięcia poziomu .
Możesz założyć, że dla każdej operacji cofnięcia będzie istniała wcześniejsza operacja niższego poziomu w stanie aktywnym, która będzie mogła zostać cofnięta.
Twój program powinien wypisać wierszy. -ty wiersz wyjścia powinien zawierać jedną liczbę całkowitą - stan edytora po wykonaniu pierwszych operacji podanych na wejściu.
Dla danych wejściowych:
11 1 2 5 -1 -1 -3 4 -2 -1 -1 1
poprawną odpowiedzią jest:
1 2 5 2 1 2 4 2 1 0 1
Podzadanie | Ograniczenia | Punkty |
1 | 20 | |
2 | , jedynie operacje oraz | 15 |
3 | , oceniana jest wyłącznie ostatnia wypisana liczba (uwaga: pozostałe liczb wciąż muszą się zawierać między a ) | 28 |
4 | 37 |